package com.jxb.three;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 思路：
 *  1：首先对数组进行排序
 *  2：通过双指针实现
 *      1：遍历数组
 *      2：第一个指针指向第二个元素，第二个指针指向第三个元素
 *      3：比较是否等于0，若等于0，添加到集合中
 *      4：对第二个元素和下一个元素相等进行去重，对第三个元素和前一个元素相等进行去重
 *      5：对第一个元素与下一个元素相等进行去重
 */
public class ThreeSum_15 {
    public static void main(String[] args) {

    }

    //排序(O(logn))+双指针(O(n^2))
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums.length < 3) {
            return results;
        }
        //进行排序
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0;i<n;i++) {
            //若第一个数大于0，那么所有数都大于0
            if (nums[i] > 0) {
                break;
            }
            //定义双指针
            int head = i+1;
            int tail = n-1;
            //head和tail相向而行
            while (head < tail) {
                int sum = nums[i] + nums[head] + nums[tail];
                //小于0，左边元素太小需要往右移动
                if (sum < 0) {
                    head++;
                }
                //大于0，右边元素太大需要往左移动
                else if (sum > 0) {
                    tail--;
                }
                //相等，将数组进行记录
                else {
                    List<Integer> els = new ArrayList<>();
                    els.add(nums[i]);
                    els.add(nums[head]);
                    els.add(nums[tail]);
                    results.add(els);
                    //对head和head+1的元素相等进行去重
                    while (head + 1 <= tail && nums[head] == nums[head + 1]) {
                        head++;
                    }
                    //对tail和tail-1的元素相等进行去重
                    while (head + 1 <= tail && nums[tail] == nums[tail - 1]) {
                        tail--;
                    }
                    head++;
                    tail--;
                }
            }
            //对第一个元素重复，进行去重
            while (i+1 < n && nums[i+1] == nums[i]) {
                i++;
            }
        }
        return results;
    }


}
